package com.wang.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: along
 * @Create: 2021/9/3
 * @Description:leetcode面试题17.14 最小k个数
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 * 示例：
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 */
public class Solution17 {
    //常规 直接全排序 返回前k个数即可 时间复杂度nlogN 空间复杂度logN
    public static int[] smallestK1(int[] arr, int k) {
        int[] res = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k ; ++i) {
            res[i] = arr[i];
        }
        return res;
    }
    //利用优先队列的特性 先输出最小值
    public static int[] smallestK2(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int[] res = new int[k];
        for (int i : arr) {
            q.offer(i);
        }
        for (int i = 0; i < k; i++) {
            res[i] = q.poll();
        }
        return res;
    }

}
